//某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。 
//
// 
//
// 示例 1： 
//
// 
//输入：records = [0,1,2,3,5]
//输出：4
// 
//
// 示例 2： 
//
// 
//输入：records = [0, 1, 2, 3, 4, 5, 6, 8]
//输出：7 
//
// 
//
// 提示： 
//
// 1 <= records.length <= 10000 
//
// Related Topics 位运算 数组 哈希表 数学 二分查找 👍 441 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-05-16 19:35:16
 * @description LCR 173.点名
 
 */
 
public class QueShiDeShuZiLcof {
    public static void main(String[] args) {
    //测试代码
    QueShiDeShuZiLcof fun = new QueShiDeShuZiLcof();
    Solution solution= fun.new Solution();
        System.out.println(solution.takeAttendance(new int[]{1,0,4,3,5}));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //二分，因为如果都不缺席，那么坐标就是学号
    //否则缺席后的都会变成坐标-1
    //所以二分查找，找到第一个坐标和学号不相等的
    public int takeAttendance1(int[] records) {
        int l=0,r=records.length-1;
        while (l<=r){
            int m=l+(r-l)/2;
            if(records[m]==m){
                l=m+1;
            }else{
                r=m-1;
            }
        }
        return l;
    }

    public int takeAttendance(int[] records) {
        int missing = records.length; // 初始化为 n，防止所有 records[i] == i 的情况
        for (int i = 0; i < records.length; i++) {
            //如果 records[i] == i，说明这个学号没有缺席
            //否则就说明这个学号缺席了
            // 异或所有可能的学号和实际存在的学号，最终剩下的就是缺失的学号
            //即使没有按照顺序，也能找到缺失的学号
            //i^i=0，只需要列举出所有的，最后没出现的一定还是原值
            missing ^= i ^ records[i];
        }
        return missing;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
